package algotithm.weekendrace.leetcode283.test4;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author tom
 * @date 2022-03-06 17:51
 */
class Solution {
    public List<Integer> replaceNonCoprimes(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        for (int num : nums) {
            int cur = num;
            while (!stack.isEmpty()) {
                int p = stack.peek();
                long x = gcd(cur, p);
                // 非互质
                if (x > 1) {
                    stack.pop();
                    cur = (int) (p / x * cur);
                } else {
                    break;
                }
            }
            stack.push(cur);
        }
        return new ArrayList<>(stack);
    }


    public long gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}